Cryptographic systems are concerned with confidentiality, authenticity, integrity, and non-repudiation of data sent from a first party to a second party. Modern cryptographic schemes based on the discrete logarithm problem in a finite abelian group are designed to address these concerns. One such finite abelian group, which is becoming increasingly popular, is a group of points on an elliptic curve (EC) over a finite field with group operation provided by simple algebraic formulae. This is because such group operations are relatively simple to realize in hardware or software. However, to fully realize implementation efficiencies of using such group, system designers need to pay close attention to underlying implementations of associated field arithmetic.
For example, in scenarios where field inversions are significantly more expensive than multiplication, it is typically more efficient to utilize weighted projective coordinates so that point addition can be performed using field multiplications, as described by Blake et al, “Elliptic Curves in Cryptography”, Cambridge University Press, 1999, page 59-60, and defer field inversions (usually only one such inversion operation is implemented at the end of a long sequence of multiplications). However, the computational cost of eliminating inversions is that an increased number of multiplications must generally be calculated. An efficient method from multiplying two elements in a finite group G is essential to performing efficient exponentiation.
Exponentiation is commonly used in public-key cryptography to calculate a scalar multiple n of points P on an elliptic curve, where n is a very large integer (e.g., a random number or private key), and wherein P is a weighted projective coordinate. An unsophisticated way to compute nP is to do n−1 multiplications in the group G. For cryptographic applications, the order of the group G typically exceeds 2160 elements, and may exceed 22024 elements. Such operations are computationally intensive, and most choices of n are large enough that it becomes infeasible to calculate nP using n−1 successive multiplications by P. However, there are a number of techniques that can be used to reduce the computational costs of exponentiation.
For instance, repeated square-and-multiply algorithms (i.e., binary exponentiation) and windowing methods such as described by Blake et al, “Elliptic Curves in Cryptography”, Cambridge University Press, 1999, pages 63-72, can reduce the computational costs of exponentiation. More particularly, repeated square-and-multiply algorithms divide the exponent n into smaller sums of powers of two (2), which respectively take less processing resources to compute. For instance, given a projective point P with coordinates (x, y, z) on an elliptic curve over a finite field, n can be divided into pieces of size 23 (i.e., using a window of 3) to calculate scalar multiples of P (23P, or 8P) with multiple point doubling iterations. To accomplish this, existing systems typically input P=(x, y, z) into the square-and-multiply algorithm to generate 2P. Next, the coordinates for 2P (output from the first doubling operation) are input as (x, y, z) into the same square-and-multiply algorithm to obtain 4P. Finally, this iterative process is repeated one more time to input the coordinates for 4P (output from the second doubling operation) as (x, y, z) into the same square-and-multiply algorithm to obtain 8P. This process to obtain 8P involves a total of 30 field multiplications.